package com.kevinkk.dp;

/**
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 */

/**
 * 1. dp 数组的含义
 *      dp[i] 表示 i 个节点能组成的BST数量
 * 2. dp 公式
 *      dp[i] += dp[j] * dp[i - j - 1];
 *      i 个节点可以拆分为，左边 j 个节点，右边 i-j-1 个节点
 *      那能组成的树的数量就是二者的乘积
 * 3. dp 数组的初始化
 *      dp[0] 肯定是为 1 的
 *      这里考虑要不要对 dp[1] 进行初始化
 *      其实 dp[1] 是可以通过上述递推公式得出的，因此不用初始化
 * 4. dp 数组的遍历方式
 */

public class UniqueBinarySearchTrees {
    class Solution {
        public int numTrees(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < i; j++) {
                    dp[i] += dp[j] * dp[i - j - 1];
                }
            }

            return dp[n];
        }
    }
}
